//
// Created by Tan Ke on 2024/1/4.
//

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*
 * 设 F(k, i, j)为从棋盘(i, j)开始起跳, 经过k轮后仍在棋盘上的概率
 * 对每个F(k, i, j), 我们有:
 *
 * F(k, i, j) = [F(k-1, i-2, j+1) + F(k-1, i-2, j-1) + F(k-1, i-1, j+2) + F(k-1, i-1, j-2) + F(k-1, i+1, j+2) + F(k-1, i+1, j-2) + F(k-1, i+2, j+1) + F(k-1, i+2, j-1)] / 8
 *
 * 也就是说, F(k, i, j) 的概率值, 等于它所有下一跳后的 F(k-1, next_i, next_j)的值相加, 再除以8
 *
 * 因此, 可以使用动态规范的方法来解决这道题
 */

double calcFunc(double*** traceMap, int n, int k, int i, int j)
{
    /* 此时已经在棋盘外, 返回0 */
    if (i < 0 || i >= n || j < 0 || j >= n) {
        return 0.0;
    }

    /* 此时已经完成了 k 步, 且棋子依然在棋盘内 */
    if (k == 0) {
        traceMap[k][i][j] = 1.0;
        return 1.0;
    }

    /* 如果之前已经计算过 F(k, i, j), 那么就直接返回结果 */
    if (traceMap[k][i][j] >= 0.0) {
        return traceMap[k][i][j];
    }

    /* 如果没有计算过, 那么分别计算8个方位的F(k-1, next_i, next_j) */
    double prob_1 = calcFunc(traceMap, n, k-1, i-2, j+1);
    double prob_2 = calcFunc(traceMap, n, k-1, i-2, j-1);
    double prob_3 = calcFunc(traceMap, n, k-1, i-1, j+2);
    double prob_4 = calcFunc(traceMap, n, k-1, i-1, j-2);
    double prob_5 = calcFunc(traceMap, n, k-1, i+1, j+2);
    double prob_6 = calcFunc(traceMap, n, k-1, i+1, j-2);
    double prob_7 = calcFunc(traceMap, n, k-1, i+2, j+1);
    double prob_8 = calcFunc(traceMap, n, k-1, i+2, j-1);

    traceMap[k][i][j] = (prob_1 + prob_2 + prob_3 + prob_4 + prob_5 + prob_6 + prob_7 + prob_8) / 8.0;

    return traceMap[k][i][j];
}

double knightProbability(int n, int k, int row, int column)
{
    if (k == 0) {
        return 1.0;
    }
    /* 分配一个三维数组, 存储F(k, i, j) */
    double ***f = (double***)malloc(sizeof(double**) * k);

    for (int w = 0; w <= k; w ++) {
        double **map = (double**)malloc(sizeof(double*) * n);
        for (int i = 0; i < n; i ++) {
            map[i] = (double*)malloc(sizeof(double) * n);
            for (int j = 0; j < n; j ++) {
                map[i][j] = -1.0;
            }
        }
        f[w] = map;
    }

    return calcFunc(f, n, k, row, column);
}

int main(void)
{
    printf("%lf\n", knightProbability(3, 2, 0, 0));
    printf("%lf\n", knightProbability(1, 0, 0, 0));

    return 0;
}
